package org.yinxianren.www.study_02.study.arithmetic.primarysort;


import org.junit.Test;
import org.yinxianren.www.study_02.study.arithmetic.IArithmetic;
import org.yinxianren.www.study_02.study.arithmetic.IPrint;

/**
 *
 * 希尔排序
 *
 *
 */
public class Shell implements IArithmetic, IPrint {

    /**
     *
     * 0 1 2 3 5 6 7 7 7 8 8 9 12 41 45 45 54 56 58 65 98 98 99 289 874
     *
     */
    @Test
    public void sort(){
        Comparable[] array={58,9,874,54,289,0,45,8,98,7,45,12,65,2,1,3,6,99,8,7,5,7,41,56,98};
        int len=array.length;
        int h=1;
        //确认分段因子
        while(h < len/3)
          h = 3*h + 1;  //1,4,13,40,121,364,1093


        while(h >= 1){
          for(int i=h ;i<len;i++){
              for(int j=i;j>=h && less(array[j],array[j-h]);j -=h ){
                  exch(array,j,j-h);
              }
          }
          h=h/3;
        }
        show(array);
    }


}
